#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MAXN = 2e6+11;
LL prime[MAXN], p_cnt, mu[MAXN];
bool not_p[MAXN];
map<LL, LL> muAns;
void Init() {
    p_cnt = 0;
    mu[1] = 1;
    for (LL i=2; i<MAXN; ++i) {
        if (!not_p[i]) {
            prime[p_cnt++] = i;
            mu[i] = -1;
        }
        for (LL j=0; j<p_cnt&&i*prime[j]<MAXN; ++j) {
            not_p[i*prime[j]] = true;
            if (i%prime[j] == 0) {
                mu[i*prime[j]] = 0;
                break;
            }
            mu[i*prime[j]] = -mu[i];
        }
    }
    mu[0] = 0;
    for (LL i=1; i<MAXN; ++i) {
        mu[i] += mu[i-1];
    }
}
LL muSum(LL n) {
    if (n<MAXN) return mu[n];
    if (muAns.count(n)) return muAns[n];
    LL ret = 1;
    for (LL i=2, last; i<=n; i=last+1) {
        last = n/(n/i);
        ret -= (last-i+1)*muSum(n/i);
    }
    muAns[n] = ret;
    return ret;
}
LL f_p[32], f_c;
bool Feijie(LL* f_prime, LL& f_cnt, LL n) {
    f_cnt = 0;
    for (LL i=0; i<p_cnt&&n!=1; ++i) {
        if (n%prime[i] == 0) {
            LL t = prime[i];
            LL cnt = 0;
            f_prime[f_cnt++] = t;
            while(n%t==0) {
                n /= t;
                ++cnt;
            }
            if (cnt>1) return false;
        }
    }
    if (n != 1) f_prime[f_cnt++] = n;
    return true;
}
LL solve(LL m, LL n) {
    if (n==1) return muSum(m);
    if (m==0 || n==0) return 0;
    LL f_prime[25];
    LL f_cnt=0;
    for (int i=0; i<f_c; ++i) {
        if (n%f_p[i] == 0) {
            f_prime[f_cnt++] = f_p[i];
        }
    }
    LL len = (1ll<<f_cnt);
    LL ret = 0;
    for (LL i=0; i<len; ++i) {
        LL d = 1;
        LL cnt = 0;
        for (LL j=0; j<f_cnt; ++j) {
            if (i&(1ll<<j)) {
                ++cnt;
                d *= f_prime[j];
            }
        }
        LL x = solve(m/d, d);
        if (cnt&1) ret -= x;
        else ret += x;
    }
    if (f_cnt&1) ret = -ret;
    return ret;
}

int main() {
#ifdef hai
    freopen("in.txt", "r", stdin);
#endif
    Init();
    LL m,n;
    while (~scanf("%lld %lld", &m, &n)) {
        bool flag = Feijie(f_p, f_c, n);
        if (!flag) printf("0\n");
        else printf("%lld\n", solve(m, n));
    }
    return 0;
}
